package algorthm.systemTraning.unionSearch;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import util.RandomUtil;

/**
 * @className: FiendCircle
 * @Description:
 * @Author: wangyifei
 * @Date: 2024/4/25 9:16
 */
public class FiendCircle {
    private static Logger logger = LoggerFactory.getLogger(FiendCircle.class);
    /**
     * 给 m*n 这么大小的二维数组，x-y 位置的如果为 1 ，则表示 x 和 y 相互认识，并且 y-x 也为 ，否则 x-y = y-x = 0 ,
     * 查找有多少个朋友圈
     */
    public static void main(String[] args) {
        for(int a = 0 ; a < 100000 ; a++){
            int col = RandomUtil.randIntRange(2, 10, 15);
            int row = col ;
            int[][] friends = new int[row][col];
            for(int i = 0 ; i < friends.length ; i++){
                for(int j = i + 1 ; j < friends[i].length ; j++){
                    friends[i][j] = ( RandomUtil.randBoolean() ? 1 : 0 );
//                    System.out.print(friends[i][j] + " ");
                }
            }
            int i1 = friendCircle1(friends);
            int i2 = friendCircle(friends);
            if(i1 != i2){
                System.out.println("Oops, unionSet: " + i1 + " , recursion: " + i2);
                for(int i = 0 ; i < friends.length ; i++){
                    for(int j = 0 ; j < friends[i].length ; j++){
                        System.out.print(friends[i][j] + " ");
                    }
                    System.out.println();
                }
                return ;
            }
        }

    }
    public static int friendCircle1(int[][] friends){
        int[] parents = new int[friends.length * friends[0].length];
        int size = 0 ;
        int[] help = new int[friends.length * friends[0].length];
        int col = friends[0].length;
        int row = friends.length ;
        int[] sizeSet = new int[friends.length * friends[0].length];
        UnionSet us = new UnionSet(parents , size , help , col , row , sizeSet);
        for(int i = 0 ; i < friends.length ; i++){
            for(int j = i + 1 ; j < friends[i].length ; j++){
                if(1 == friends[i][j]){
                    int index = us.index(i ,j);
                    parents[index] = index ;
                    size++;
                    sizeSet[index] = 1 ;
                }
            }
        }
        us.size = size ;
        us.sizeSet = sizeSet ;
        us.parents = parents ;
        // 合并第一行的数字
        for(int i = 1 ; i < friends[0].length ; i++){
           if(friends[0][i - 1] == 1 && friends[0][i] == 1){
                us.union(0 , i -1 , 0 , i);
           }
        }
//        for(int i = 1 ; i < friends.length ; i ++){
//            if(friends[i - 1][0] == 1 && friends[i][0] == 0){
//                us.union(i -1 , 0 , i , 0);
//            }
//        }
        for(int i = 1 ; i < friends.length  ; i++){
            for(int j = i + 1 ; j < friends[i].length ; j++){
                if(friends[i][j] == 1 && friends[i][j -1] == 1 && i < j){
                    us.union(i , j , i , j - 1);
                }
                if(friends[i][j] == 1 && friends[i - 1][j] == 1 && i < j){
                    us.union(i , j , i - 1 , j );
                }
            }
        }
        return us.size ;
    }
    public static class UnionSet{
        public int[] parents;
        public int size ;
        public int[] help ;
        public int col ;
        public int row ;
        public int[] sizeSet ;
        public UnionSet(int[] p , int s , int[] h , int c , int r , int[] sizeSet){
            parents = p ;
            size = s ;
            help = h ;
            col = c ;
            row = r ;
            this.sizeSet = sizeSet ;
        }
        public int index(int x , int y){
            return x * col + y ;
        }
        public void union(int x , int y , int i , int j){
            int xyFather = find(x , y);
            int ijFather = find(i , j);
            if(xyFather != ijFather){
                int big = (sizeSet[xyFather] > sizeSet[ijFather] ? xyFather : ijFather);
                int small = (sizeSet[xyFather] <= sizeSet[ijFather] ? xyFather : ijFather);
                parents[small] = big ;
                sizeSet[big] += sizeSet[small];
                sizeSet[small] = 0 ;
                size--;
            }
        }
        public int find(int x , int y){
            int idx = 0 ;
            int cur = index(x , y); ;
            while( cur != parents[cur]){
                cur = parents[cur];
                help[idx++] = cur ;
            }
            idx--;
            while(idx >= 0){
                parents[help[idx]] = cur ;
                idx--;
            }
            return cur;
        }

    }
    public static int friendCircle(int[][] friends){
        int size = 0 ;
        for(int i = 0 ; i < friends.length ; i++){
            for(int j = i ; j < friends[i].length ; j++){
                if(1 == friends[i][j]){
                    size++;
                    infect(friends , i , j);
                }
            }

        }
        return size ;
    }
    public static void infect(int[][] friends , int x , int y){
        if(x < 0 || x >= friends.length || y < 0 || y >= friends[0].length || x > y){
            return;
        }
        if(friends[x][y] == 1){
            friends[x][y] = 2 ;
            infect(friends , x - 1 , y);
            infect(friends , x + 1 , y);
            infect(friends , x , y - 1);
            infect(friends , x , y + 1);
        }
    }
}
